package com.lwx.algorithm;

import java.util.*;

//用递归的方法实现三角形的最短路径
public class Triangle1 {
    //记录到(i,j)的最小值
    static ArrayList<ArrayList<Integer>> minList = new ArrayList<>();
    /**
     * 返回
     * @param triangle
     * @return
     */
    public static int minimumTotal(List<List<Integer>> triangle) {
        return minimumAtIndex(triangle.size(),triangle.get(triangle.size()-1).size(),triangle);
    }

    /**
     * 从三角形顶部，到第i行，j列时的最小值
     * @param i
     * @param j
     * @param ele
     * @return
     */
    public static int minimumAtIndex(int i, int j , List<List<Integer>> ele){
        if(j == 0){
            //三角形矩阵的最左边那一列
            return minimumAtIndex(i-1, j ,ele) + minList.get(i).get(j);
        }else if(j == i){
            //三角形矩阵的最右边那一列
            return minimumAtIndex(i-1, j-1 ,ele) + minList.get(i).get(j);
        }else {

        }
        if(i == 0){
            return ele.get(i).get(j);
        }else if(i == 1){
            int row0 = ele.get(0).get(0);
            return Math.min(row0+ele.get(1).get(0),row0+ele.get(1).get(1));
        }
        return Math.min(minimumAtIndex(i-1,j,ele),minimumAtIndex(i-1,j-1,ele))+ele.get(i).get(j);
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> ele1 = new ArrayList<>();
        ele1.add(2);
        triangle.add(ele1);
        List<Integer> ele2 = new ArrayList<>();
        ele2.add(3);
        ele2.add(4);
        triangle.add(ele2);
        List<Integer> elel3 = new ArrayList<>();
        elel3.add(6);
        elel3.add(5);
        elel3.add(7);
        triangle.add(elel3);
        List<Integer> ele4 = new ArrayList<>();
        ele4.add(4);
        ele4.add(1);
        ele4.add(8);
        ele4.add(3);
        triangle.add(ele4);
        int result = minimumTotal(triangle);
        System.out.println(result);
    }
}
